DROPS

Document

DOI: 10.4230/LIPIcs.SOCG.2015.451

Restricted Isometry Property for General p-Norms

Authors: Zeyuan Allen-Zhu, Rati Gelashvili, and Ilya Razenshteyn

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

The Restricted Isometry Property (RIP) is a fundamental property of a matrix which enables sparse recovery. Informally, an m x n matrix satisfies RIP of order k for the L_p norm, if |Ax|_p is approximately |x|_p for every x with at most k non-zero coordinates. For every 1 <= p < infty we obtain almost tight bounds on the minimum number of rows m necessary for the RIP property to hold. Prior to this work, only the cases p = 1, 1 + 1/log(k), and 2 were studied. Interestingly, our results show that the case p=2 is a "singularity" point: the optimal number of rows m is Theta(k^p) for all p in [1, infty)-{2}, as opposed to Theta(k) for k=2. We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss implications of our results for the Stable Sparse Recovery problem.

Cite as

Zeyuan Allen-Zhu, Rati Gelashvili, and Ilya Razenshteyn. Restricted Isometry Property for General p-Norms. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 451-460, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{allenzhu_et_al:LIPIcs.SOCG.2015.451,
  author =	{Allen-Zhu, Zeyuan and Gelashvili, Rati and Razenshteyn, Ilya},
  title =	{{Restricted Isometry Property for General p-Norms}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{451--460},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.451},
  URN =		{urn:nbn:de:0030-drops-51273},
  doi =		{10.4230/LIPIcs.SOCG.2015.451},
  annote =	{Keywords: compressive sensing, dimension reduction, linear algebra, high-dimensional geometry}
}

Search Results

Documents authored by Razenshteyn, Ilya

Restricted Isometry Property for General p-Norms

Abstract

Cite as

Thanks for your feedback!

Could not send message